package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.TraverseUtils;

/*
 * 
原题　
		  Follow up for "Remove Duplicates":
	What if duplicates are allowed at most twice?
	
	For example,
	Given sorted array nums = [1,1,1,2,2,3],
	
	Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length. 
题目大意
	跟踪“删除重复”：
	如果最多允许重复一次两次？
	
	例如，
	给定排序数组nums = [1,1,1,2,2,3]，
	
	你的函数应该返回长度= 5，前五个元素的数字是1，2，2和3.不管你​​离开新的长度什么都不重要。
解题思路
	@_026_Remove_Duplicates_from_Sorted的思路	
	加一个count计算元素出现的次数
 * @Date 2017-10-08 22：33
 */
public class _080_Remove_Duplicates_from_Sorted_Array_II {
	
//	public int removeDuplicates(int[] nums) {
//		int len = 0;						//长度结果
//		if (nums==null || nums.length==0)	return len;
//		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
//		for (int i = 0; i < nums.length; i ++) {
//			int num = nums[i];
//			if (!map.containsKey(num)) {
//				map.put(num, 1);
//			} else if (map.containsKey(num) && map.get(num)<2) {
//				map.put(num, map.get(num)+1);
//			} else {
//				continue;
//			}
//		}
//		
//		for (Integer num : map.keySet()) {
//			len += map.get(num);
//		}
//		return len;	 
//	}
	
	/**
	 * @My 
	 * @param nums
	 * @return
	 */
	public int removeDuplicates(int[] nums) {
		if (nums==null || nums.length==0)	return 0;
		int pre = nums[0];
		int count = 1;			//记录当前元素数字重复的次数(<2)
		int end = 1;
		for (int i = 1; i < nums.length; i ++) {
			if (nums[i] != pre) {
				nums[end] = nums[i];
				pre = nums[end];
				end++;
				count = 1;
			} else {
				if (count < 2) {
					nums[end] = nums[i];
					pre = nums[end];
					end++;
					count++;
				} else {
					continue;
				}
			}
		}
		TraverseUtils.println(nums, end);
		LogUtils.br();
		return end;	 
	}
	public static void main(String[] args) {
		_080_Remove_Duplicates_from_Sorted_Array_II obj = new _080_Remove_Duplicates_from_Sorted_Array_II();
		LogUtils.println("80", 
				obj.removeDuplicates(new int[] {1,1}));
	}

}
